package com.zyk.leetcode;

import java.util.*;

/**
 * @author zhangsan
 * @date 2021/4/21 14:08
 */
public class C30 {

    Set<String> group;

    public List<Integer> findSubstring(String s, String[] words) {
        group = new HashSet<>();
        fullPermutation(words, 0, new StringBuilder());
        List<Integer> ans = new ArrayList<>();
        for (String s1 : group) {
            int p = s.indexOf(s1);      // indexof有毒, 还得考虑中间后边情况
            if (p >= 0) ans.add(p);
        }
        return ans;
    }

    public void fullPermutation(String[] words, int i, StringBuilder sb) {
        if (i == words.length)
            group.add(sb.toString());

        for (int j = i; j < words.length; j++) {
            swap(words, i, j);
            sb.append(words[i]);
            fullPermutation(words, i + 1, sb);
            sb.delete(sb.length() - words[i].length(), sb.length());
            swap(words, i, j);
        }
    }

    public void swap(String[] words, int i, int j) {
        String tmp = words[i];
        words[i] = words[j];
        words[j] = tmp;
    }

    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) return res;
        HashMap<String, Integer> map = new HashMap<>();
        int one_word = words[0].length();
        int word_num = words.length;
        int all_len = one_word * word_num;
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < one_word; i++) {
            int left = i, right = i, count = 0;
            HashMap<String, Integer> tmp_map = new HashMap<>();
            while (right + one_word <= s.length()) {
                String w = s.substring(right, right + one_word);
                right += one_word;
                if (!map.containsKey(w)) {
                    count = 0;
                    left = right;
                    tmp_map.clear();
                } else {
                    tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
                    count++;
                    while (tmp_map.getOrDefault(w, 0) > map.getOrDefault(w, 0)) {
                        String t_w = s.substring(left, left + one_word);
                        count--;
                        tmp_map.put(t_w, tmp_map.getOrDefault(t_w, 0) - 1);
                        left += one_word;
                    }
                    if (count == word_num) res.add(left);
                }
            }
        }
        return res;
    }



    // for test
    public static void main(String[] args) {

        C30 test = new C30();
        String s = "barfoothefoobarman";
        String[] words = {"foo", "bar"};
        System.out.println(test.findSubstring(s, words));
        System.out.println(test.findSubstring2(s, words));
    }


}
